import heapq
from typing import List

class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        # dijkstra
        queue = [(0, (0, 0))]  # 代价，坐标
        m = len(grid)
        n = len(grid[0])

        inf = float('inf')
        min_dis = [[inf for _ in range(n)] for _ in range(m)]
        while queue:
            min_cost, (x, y) = heapq.heappop(queue)
            # 将箭头所指方向入堆
            if grid[x][y] == 1:
                nx, ny = x, y + 1
            elif grid[x][y] == 2:
                nx, ny = x, y - 1
            elif grid[x][y] == 3:
                nx, ny = x + 1, y
            else:
                nx, ny = x - 1, y
            if 0 <=nx < m and 0 <= ny < n and min_dis[nx][ny] > min_cost:
                min_dis[nx][ny] = min_cost
                heapq.heappush(queue, (min_cost, (nx, ny)))
            for nx, ny in [(x, y + 1),(x, y - 1),(x + 1, y),(x - 1, y)]:
                if 0 <= nx < m and 0 <= ny < n and min_dis[nx][ny] > min_cost + 1:
                    min_dis[nx][ny] = min_cost + 1
                    heapq.heappush(queue, (min_cost + 1, (nx, ny)))
        return min_dis[m-1][n-1]

if __name__ == '__main__':
    s = Solution()
    r = s.minCost(grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]])
    print(r)

